高考申論題
109年
[資訊處理] 資料結構
第 一 題
📖 題組：
一、考慮數字1到n，若將其順序重新排置，每個排列順序都稱作一個排列或置換（Permutation），例如5 1 4 3 2是1 2 3 4 5的一個排列。我們可以將一個數字1到n的排列視為一個順序的映射P，則前述例子可表示為P(5) = 1、P(1) = 2、P(4) = 3、P(3) = 4、P(2) = 5。當然，1 2 3 4 5也是1 2 3 4 5的一個排列。在一個數字1到n的排列P中，若一對數字 i和 j，1 ≤ i < j ≤ n，P( j) < P(i)，也就是在排列P中較大的數字 j出現在較小的數字 i左邊（前面），我們稱此對數字為反向（Inversion），而排列P的反向數（Inversion number）則定義為排列P中反向的總數量。請回答下列問題：
一、考慮數字1到n，若將其順序重新排置，每個排列順序都稱作一個排列或置換（Permutation），例如5 1 4 3 2是1 2 3 4 5的一個排列。我們可以將一個數字1到n的排列視為一個順序的映射P，則前述例子可表示為P(5) = 1、P(1) = 2、P(4) = 3、P(3) = 4、P(2) = 5。當然，1 2 3 4 5也是1 2 3 4 5的一個排列。在一個數字1到n的排列P中，若一對數字 i和 j，1 ≤ i < j ≤ n，P( j) < P(i)，也就是在排列P中較大的數字 j出現在較小的數字 i左邊（前面），我們稱此對數字為反向（Inversion），而排列P的反向數（Inversion number）則定義為排列P中反向的總數量。請回答下列問題：
數字1到n的何種排列會有最大的反向數？最大反向數是多少？（5分）
📝 此題為申論題
思路引導 VIP
看到本題，首先要辨識出這是關於「反向（Inversion）」定義的基礎數學題。可以先舉個例子思考：什麼時候任何兩個數字都會形成反向？答案是當所有較大的數字都在較小的數字前面時。接著利用排列組合的觀念，計算從 n 個數字中任取 2 個的組合數，即為最大反向數。
🤖
AI 詳解
AI 專屬家教
【考點分析】 排列（Permutation）與反向數（Inversion Number）的定義、組合數學概念。 【理論/法規依據】
▼ 還有更多解析內容